package com.sjf.day02.tree;

import sun.reflect.generics.tree.Tree;

import java.lang.reflect.Field;

/**
 * 二叉树
 *
 * @author <huangtang>
 * @since 2022/1/5 14:22
 **/
public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        //创建树节点
        TreeNode root = new TreeNode(1);
        TreeNode Node2 = new TreeNode(2);
        TreeNode Node3 = new TreeNode(3);
        TreeNode Node4 = new TreeNode(4);
        TreeNode Node5 = new TreeNode(5);
        binaryTree.root = root;  //    1
        root.left = Node2;      //  2     3
        root.right = Node3;    //       5     4
        Node3.right = Node4;
        Node3.left = Node5;

        System.out.println("前序遍历");
        binaryTree.preOrder();//12354
        //binaryTree.delNode(4);
        //binaryTree.delNode(3);
        //System.out.println("删除后");
        //binaryTree.preOrder();//1234



        //System.out.println("中序查找");
        //binaryTree.midOrderSearch(5);
        //
        //System.out.println("后序查找");
        //binaryTree.AfterOrderSearch(5);


        //System.out.println("前序遍历");
        //binaryTree.preOrder();//12354

        //System.out.println("中序遍历");
        //binaryTree.midOrder();//21534

        System.out.println("后序遍历");
        binaryTree.AfterOrder();//25431

        System.out.println("树节点个数"+ binaryTree.getSize());
    }
}

/**
 * 二叉树
 */
class BinaryTree{

    public TreeNode root; //根节点
    public int size;//节点个数

    public int getSize() {
        return numberOfTree(root);
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        if(root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 前序查找
     * @param id 查找的id
     */
    public void preOrderSearch(int id){
        if(root!=null){
            TreeNode treeNode = this.root.preOrderSearch(id);
            if(treeNode == null){
                System.out.println("未找到节点");
            }
        }else{
            System.out.println("二叉树为空，无法查找");
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(root!=null){
            this.root.midOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 中序查找
     * @param id 查找的id
     */
    public void midOrderSearch(int id){
        if(root!=null){
            TreeNode treeNode = this.root.midOrderSearch(id);
            if(treeNode == null){
                System.out.println("未找到节点");
            }
        }else{
            System.out.println("二叉树为空，无法查找");
        }
    }

    /**
     * 后序遍历
     */
    public void AfterOrder(){
        if(root!=null){
            this.root.AfterOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 后序查找
     */
    public void AfterOrderSearch(int id){
        if(root!=null){
            TreeNode treeNode = this.root.AfterOrderSearch(id);
            if(treeNode == null){
                System.out.println("未找到节点");
            }
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    /**
     * 删除节点
     * @param id 节点id
     */
    public void delNode(int id){
        if(root!=null){
            //先判断root是否是删除节点
            if(root.id == id){
                root = null;
            }else{
                root.delNode(id);
            }
        }else {
            System.out.println("树为空，无法删除");
        }
    }

    /**
     * 获取树节点的个数
     * @param treeNode 当前节点
     * @return 当前节点下的子节点个数
     */
    public int numberOfTree(TreeNode treeNode){
        if(treeNode==null){
            return size;
        }
        size++;
        //递归左遍历
        if(treeNode.left!=null){
            numberOfTree(treeNode.left);
        }
        if(treeNode.right!=null){
            numberOfTree(treeNode.right);
        }
        return size;
    }

}

/**
 * 创建树节点
 */
class TreeNode{
    public int id;
    public TreeNode left;
    public TreeNode right;
    public  static int count1;//比较次数
    public  static int count2;//比较次数
    public  static int count3;//比较次数

    public TreeNode(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "id=" + id +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        //先输出父节点
        System.out.println(this);
        //递归左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //递归右子树
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    /**
     * 前序查找
     */
    public TreeNode preOrderSearch(int id){
        count1++;
        if(this.id == id){
            System.out.println("找到节点"+this);
            System.out.println("比较次数"+count1);
            return this;
        }
        if(this.left!=null){
            //递归左子树
            this.left.preOrderSearch(id);
        }
        if(this.right!=null){
            //递归右子树
            this.right.preOrderSearch(id);
        }
        return null;
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        //先递归左子树
        if(this.left!=null){
            this.left.midOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归右子树
        if(this.right!=null){
            this.right.midOrder();
        }
    }

    /**
     * 中序查找
     */
    public TreeNode midOrderSearch(int id){
        if(this.left!=null){
            this.left.midOrderSearch(id);
        }
        count2++;
        if(this.id == id){
            System.out.println("找到节点"+this);
            System.out.println("比较次数"+count2);
            return this;
        }
        if(this.right!=null){
            this.right.midOrderSearch(id);
        }
        return null;
    }

    /**
     * 后序遍历
     */
    public void AfterOrder(){
        if(this.left!=null){
            this.left.AfterOrder();
        }
        if(this.right!=null){
            this.right.AfterOrder();
        }
        System.out.println(this);
    }

    /**
     * 后序查找
     */
    public TreeNode AfterOrderSearch(int id){
        if(this.left!=null){
            this.left.AfterOrderSearch(id);
        }
        if(this.right!=null){
            this.right.AfterOrderSearch(id);
        }
        count3++;
        if(this.id == id){
            System.out.println("找到节点"+this);
            System.out.println("比较次数:"+count3);
            return this;
        }
        return null;
    }

    /**
     * 删除节点
     * @param id 节点id
     */
    public void delNode(int id){
        if(this.left!=null && this.left.id == id){
            //删除左子节点即可
            this.left = haveChild(this.left);
            return;
        }
        if(this.right!=null && this.right.id == id){
            this.right = haveChild(this.right);
            return;
        }
        //递归左子节点删除
        if(this.left!=null){
            this.left.delNode(id);
        }
        //递归右子节点删除
        if(this.right!=null){
            this.right.delNode(id);
        }
    }

    /**
     * 不删除子树的方法
     * @param treeNode 返回删除节点后顶替该节点的节点
     * @return
     */
    public TreeNode haveChild(TreeNode treeNode){
        //没有字节点直接删除
        if(treeNode.left == null && treeNode.right == null){
            return null;
        }
        //如果有一个节点，则让该节点顶替
        if(treeNode.left == null){
            return treeNode.right;
        }else if(treeNode.right == null){
            return treeNode.left;
        }
        //有两个节点则，则让左节点顶替
        treeNode.left.right = treeNode.right;
        return treeNode.left;
    }
}
